package leetcode.code0919;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.tree.TreeNode;

public class CBTInserter {

	TreeNode root;
	Queue<TreeNode> parents;

	public CBTInserter(TreeNode root) {
		this.root = root;
		Queue<TreeNode> queue = new LinkedList<>();
		parents = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node.left != null) {
				queue.add(node.left);
			}
			if (node.right != null) {
				queue.add(node.right);
			}
			if (node.left == null || node.right == null) {
				parents.add(node);
			}
		}
	}

	public int insert(int val) {
		TreeNode node = parents.peek();
		TreeNode newNode = new TreeNode(val);
		if (node.left == null) {
			node.left = newNode;
		} else {
			node.right = newNode;
			parents.poll();
		}
		this.parents.add(newNode);
		return node.val;
	}

	public TreeNode get_root() {
		return this.root;
	}
}
